package com.yileiqian.util;

import java.util.LinkedList;

public class Trie {

	private TrieNode root;

	public Trie() {
		root = new TrieNode('\0');
	}

	public void insert(String s) {
		TrieNode current = root;
		for (int i = 0; i < s.length(); i++) {
			TrieNode next = current.subNode(s.charAt(i));
			if (next == null) {
				next = new TrieNode(s.charAt(i));
				current.child.add(next);
			}
			current = next;
		}
		current.marker = true;
	}

	public boolean search(String s) {
		TrieNode current = root;
		for (int i = 0; i < s.length(); i++) {
			TrieNode next = current.subNode(s.charAt(i));
			if (next == null)
				return false;
			else
				current = next;
		}
		return current.marker;
	}

	public void print(TrieNode n) {
		System.out.println(n.content);
		for (TrieNode eachChild : n.child) {
			print(eachChild);
		}
	}

	public static void main(String args[]) {
		Trie trie = new Trie();
		trie.insert("USC");
		trie.insert("SCU");
		trie.insert("USCCCCC");

		// trie.print(trie.root);

		System.out.println(trie.search(""));
		System.out.println(trie.search("C"));
		System.out.println(trie.search("USC"));
		System.out.println(trie.search("SCU"));
		System.out.println(trie.search("USCC"));
		System.out.println(trie.search("USCCCCCC"));
	}
}

class TrieNode {
	char content;
	boolean marker;
	LinkedList<TrieNode> child;

	public TrieNode(char c) {
		child = new LinkedList<TrieNode>();
		marker = false;
		content = c;
	}

	public TrieNode subNode(char c) {
		if (child != null) {
			for (TrieNode eachChild : child) {
				if (eachChild.content == c) {
					return eachChild;
				}
			}
		}
		return null;
	}
}
